class Solution:
    def findDuplicate(self, nums: list) -> int:
        mid_set = set()
        for num in nums:
            if num in mid_set:
                return num
            else:
                mid_set.add(num)


class Solution2:
    def findDuplicate(self, nums: list) -> int:
        fast, slow = nums[nums[0]], nums[0]
        while fast != slow:
            fast = nums[nums[fast]]
            slow = nums[slow]
        fast = 0
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        return fast


a = Solution2()
print(a.findDuplicate([2, 5, 9, 6, 9, 3, 8, 9, 7, 1]))
print(a.findDuplicate([1,3,4,2,2]))
